package org.xqh.study.leetcode.algorithm;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LongestPalindrome
 * @Description 最长回文字符   (正序 和 倒序 内容一致)
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 * @Author xuqianghui
 * @Date 2021/1/25 18:03
 * @Version 1.0
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        System.out.println(longestPalindrome23("aacabdkacaa"));
    }

    /**
     * 官方题解
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {
                    dp[i][j] = true;
                } else if (l == 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && l + 1 > ans.length()) {
                    ans = s.substring(i, i + l + 1);
                }
            }
        }
        return ans;
    }


    /**
     * 动态规划解法  fixed
     *
     * @param s
     * @return
     */
    public static String longestPalindrome23(String s) {
        char[] array = s.toCharArray();
        int len = array.length;
        boolean[][] table = new boolean[len][len];
        int maxLen = 0;
        int maxStart = 0;
        int maxEnd = 0;
        a:
        for (int i = 0; i < len; i++) {//长度 从1 到 总长度
            b:
            for (int j = 0; j < len - i; j++) {
                if (i == 0) {
                    table[j][j + i] = true;
                } else if (i == 1) {
                    table[j][j + i] = array[j] == array[j + i];
                } else {
                    //当前位   和前一位都是 true
                    table[j][j + i] = (array[j] == array[j + i]) && table[j + 1][j + i - 1];
                }
                if (table[j][j + i] && (i + 1 > maxLen)) {
                    maxLen = i + 1;
                    maxStart = j;
                    maxEnd = j + i;
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }

    public static String longestPalindrome2(String s) {
        int maxLen = 0;
        char[] array = s.toCharArray();
        int maxStart = 0;
        int maxEnd = 0;
        a:
        for (int i = 1; i < array.length; i++) {
            b:
            for (int j = 0; j < i; j++) {
                int fs = (i - j + 2) / 2;
                boolean flag = true;
                c:
                for (int k = 0; k < fs; k++) {
                    if (array[j + k] != array[i - k]) {
                        flag = false;
                        break c;
                    }
                }
                if (flag) {
                    int len = i - j + 1;
                    if (len > maxLen) {
                        maxLen = len;
                        maxStart = j;
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }

    public static void main111(String[] args) {
        ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6))))));
        recordList(node);
        System.out.println(JSON.toJSONString(node));
    }

    static void recordList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        ListNode tmp = head;
        while (tmp != null) {
            list.add(tmp);
            tmp = tmp.next;
        }

        for (int i = 0; i < (list.size() + 1) / 2; i++) {
            int lastIdx = list.size() - i - 1;
            if (lastIdx == i + 1) {
                list.get(lastIdx).next = null;
                break;
            }
            ListNode curNext = list.get(i + 1);
            ListNode curLast = list.get(lastIdx);
            list.get(i).next = curLast;
            if (i != lastIdx) {
                curLast.next = curNext;
            } else {
                curLast.next = null;
            }
        }

    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {

        }

        ListNode(int val) {
            this.val = val;

        }

        ListNode(int val, ListNode next) {
            this.next = next;
            this.val = val;

        }

    }
}
